import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Map.Entry;


public class Main {
	public static void main(String[] args) throws Exception { new Main(); }
	int[][] scores = 
		   //   A  R  N  D  C  Q  E  G  H  I  L  K  M  F  P  S  T  W  Y  V  B  Z  X  *
		    {{4, -1, -2, -2,  0, -1, -1,  0, -2, -1, -1, -1, -1, -2, -1,  1,  0, -3, -2,  0, -2, -1,  0, -4},
		   {-1,  5,  0, -2, -3,  1,  0, -2,  0, -3, -2,  2, -1, -3, -2, -1, -1, -3, -2, -3, -1,  0, -1, -4},
		   {-2, 0,  6,  1, -3,  0,  0,  0,  1, -3, -3,  0, -2, -3, -2,  1,  0, -4, -2, -3,  3,  0, -1, -4},
		   {-2, -2,  1,  6, -3,  0,  2, -1, -1, -3, -4, -1, -3, -3, -1,  0, -1, -4, -3, -3,  4,  1, -1, -4}, 
		    {0, -3, -3, -3,  9, -3, -4, -3, -3, -1, -1, -3, -1, -2, -3, -1, -1, -2, -2, -1, -3, -3, -2, -4}, 
		   {-1,  1,  0,  0, -3,  5,  2, -2,  0, -3, -2,  1,  0, -3, -1,  0, -1, -2, -1, -2,  0,  3, -1, -4}, 
		   {-1,  0,  0,  2, -4,  2,  5, -2,  0, -3, -3 , 1, -2, -3, -1,  0, -1, -3, -2, -2,  1,  4, -1, -4}, 
		    {0, -2,  0, -1, -3, -2, -2,  6, -2, -4, -4, -2, -3 ,-3, -2,  0, -2, -2, -3, -3, -1, -2, -1, -4}, 
		   {-2,  0,  1, -1, -3,  0,  0, -2,  8, -3, -3, -1 ,-2 ,-1, -2, -1, -2, -2,  2, -3,  0,  0, -1, -4}, 
		   {-1, -3, -3, -3, -1, -3, -3, -4, -3 , 4 , 2, -3,  1,  0, -3, -2 ,-1 ,-3 ,-1 , 3 ,-3 ,-3 ,-1 ,-4}, 
		   {-1,-2,-3,-4,-1,-2,-3,-4,-3,2,4,-2,2,0,-3,-2,-1,-2,-1,1,-4,-3,-1,-4},
		{-1,2,0,-1,-3,1,1,-2,-1,-3,-2,5,-1,-3,-1,0,-1,-3,-2,-2,0,1,-1,-4},
		{-1,-1,-2,-3,-1,0,-2,-3,-2,1,2,-1,5,0,-2,-1,-1,-1,-1,1,-3,-1,-1,-4},
		{-2,-3,-3,-3,-2,-3,-3,-3,-1,0,0,-3,0,6,-4,-2,-2,1,3,-1,-3,-3,-1,-4},
		{-1,-2,-2,-1,-3,-1,-1,-2,-2,-3,-3,-1,-2,-4,7,-1,-1,-4,-3,-2,-2,-1,-2,-4},
		{1,-1,1,0,-1,0,0,0,-1,-2,-2,0,-1,-2,-1,4,1,-3,-2,-2,0,0,0,-4},
		{0,-1,0,-1,-1,-1,-1,-2,-2,-1,-1,-1,-1,-2,-1,1,5,-2,-2,0,-1,-1,0,-4},
		{-3,-3,-4,-4,-2,-2,-3,-2,-2,-3,-2,-3,-1,1,-4,-3,-2,11,2,-3,-4,-3,-2,-4},
		{-2,-2,-2,-3,-2,-1,-2,-3,2,-1,-1,-2,-1,3,-3,-2,-2,2,7,-1,-3,-2,-1,-4},
		{0,-3,-3,-3,-1,-2,-2,-3,-3,3,1,-2,1,-1,-2,-2,0,-3,-1,4,-3,-2,-1,-4},
		{-2,-1,3,4,-3,0,1,-1,0,-3,-4,0,-3,-3,-2,0,-1,-4,-3,-3,4,1,-1,-4},
		{-1,0,0,1,-3,3,4,-2,0,-3,-3,1,-1,-3,-1,0,-1,-3,-2,-2,1,4,-1,-4},
		{0,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-2,0,0,-2,-1,-1,-1,-1,-1,-4},
		{-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,1 }};
	Map<Character, Integer> scoreMap;
	Map<String, Map<String, Tuple>> save = new HashMap<String, Map<String, Tuple>>();
	
	public Main() throws Exception {
		scoreMap = new HashMap<Character, Integer>();
		scoreMap.put('A', 0); scoreMap.put('R', 1);
		scoreMap.put('N', 2); scoreMap.put('D', 3);
		scoreMap.put('C', 4); scoreMap.put('Q', 5);
		scoreMap.put('E', 6); scoreMap.put('G', 7);
		scoreMap.put('H', 8); scoreMap.put('I', 9);
		scoreMap.put('L', 10); scoreMap.put('K', 11);
		scoreMap.put('M', 12); scoreMap.put('F', 13);
		scoreMap.put('P', 14); scoreMap.put('S', 15);
		scoreMap.put('T', 16); scoreMap.put('W', 17);
		scoreMap.put('Y', 18); scoreMap.put('V', 19);
		scoreMap.put('B', 20); scoreMap.put('Z', 21);
		scoreMap.put('X', 22); scoreMap.put('-', 23);
		
		File f = new File("lab5/HbB_FASTAs.in");
		Scanner scan = new Scanner(f);
		
		Map<String, String> animals = new HashMap<String, String>();
		String dna="";
		String name = scan.nextLine().substring(1);
		while (scan.hasNext()) {
			String s = scan.nextLine();
			if (s.charAt(0) == '>') {
				animals.put(name, dna);
				dna = "";
				name=s.substring(1);
			} else {
				dna += s;
			}
		}
		
		for (Entry<String, String> e: animals.entrySet()) {
			for (Entry<String, String> g: animals.entrySet()) {
				System.out.println(e.getKey() +"--"+ g.getKey() +": "+ find(e.getValue(), g.getValue()));
			}
		}
	}
	
	Tuple find(String a, String b) {
		if (a.isEmpty() && b.isEmpty()) {
			return new Tuple(0, "", "");
		} else if (a.isEmpty()) {
			for (int i=0; i<b.length(); ++i) {
				a += "-";
			}
			return new Tuple(-4*b.length(), a, b);
		} else if (b.isEmpty()) {
			for (int i=0; i<a.length(); ++i) {
				b += "-";
			}
			return new Tuple(-4*a.length(), a, b);
		}
		
		Tuple t = fromMap(a, b);
		if (t == null) {
			t = new Tuple();
			Tuple s1 = find(a.substring(1), b);
			Tuple s2 = find(a, b.substring(1));
			Tuple s3 = find(a.substring(1), b.substring(1));
			
			int m1 = s1.score+score(a.charAt(0), '-'),
				m2 = s2.score+score('-', b.charAt(0)),
				m3 = s3.score+score(a.charAt(0), b.charAt(0));
			
			int max = max(m1, m2, m3);
			if (m1 == max) {
				t.a = a.charAt(0)+ s1.a;
				t.b = "-"+ s1.b;
				t.score = s1.score+score(a.charAt(0), '-');
			} else if (m2 == max) {
				t.a = "-"+ s2.a;
				t.b = b.charAt(0)+s2.b;
				t.score = s2.score+score('-', b.charAt(0));
			} else {
				t.a = a.charAt(0)+s3.a;
				t.b = b.charAt(0)+s3.b;
				t.score = s3.score+score(a.charAt(0), b.charAt(0));
			}
			
			if (!save.containsKey(a)) {
				save.put(a, new HashMap<String, Tuple>());
			}
			save.get(a).put(b, t);
		}
		
		return t;
	}
	
	Tuple fromMap(String a, String b) {
		if (save.containsKey(a)) {
			if (save.get(a).containsKey(b)) {
				return save.get(a).get(b);
			}
		}
		return null;
	}
	
	int max(int a, int b, int c) {
		int max = a>b? a: b;
		max = max>c? max: c;
		return max;
	}
	Tuple max(Tuple a, Tuple b, Tuple c) {
		if (a.score > b.score && a.score > c.score) {
			return a;
		} else if (b.score > a.score && b.score > c.score) {
			return b;
		} else {
			return c;
		}
	}
	
	int score(char a, char b) {
		return scores[scoreMap.get(a)][scoreMap.get(b)];
	}
}

class Tuple {
	int score;
	String a;
	String b;
	
	public Tuple() {}
	public Tuple(int s, String a, String b) {
		score = s;
		this.a = a;
		this.b = b;
	}
	
	public String toString() {
		return score +"\n"+ a +"\n"+ b;
	}
}

